#include <stdio.h>
#include <stdlib.h>

// 定义单链队列的存储结构

typedef struct QNode {

    int data;

    struct QNode *next;

}QNode,*QNodePtr;


typedef struct LinkQueue{

    //队头 队尾 指针

    QNodePtr front,rear;

}LinkQueue;

// 打印队列中的内容
void Q_Print(LinkQueue *Q) {
    printf("start print..\n");
    int i = 0;

    QNodePtr p;

    p = Q->front;

    while (Q->rear != p) {

        i++;

        // cout << p->next->data << endl;
        printf(" %d ", p->next->data);
        p = p->next;

    }

}

//插入元素e为Q的新的队尾元素
void Q_Put(LinkQueue *Q, int e) {

    QNodePtr p = (QNodePtr)malloc(sizeof(QNode));

    if (!p) // 存储分配失败

        exit(-1);

    p->data = e;

    p->next = NULL;

    //FIFO，将新节点追加到尾节点后面

    Q->rear->next = p;

    //将新的节点变成尾节点

    Q->rear = p;

}

// 构造一个空队列Q

LinkQueue* Q_Init() {

    //申请内存

    LinkQueue* Q = (LinkQueue*)malloc(sizeof(LinkQueue));

    //如果 Q 为 NULL 说明 内存申请失败，结束程序

    if (!Q)

        exit(-1);

    //初始化头尾节点 指向相同地址

    Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode));

    //如果 Q->front 为 NULL 说明 内存申请失败，结束程序

    if (!Q->front)

        exit(-1);

    Q->front->next = NULL;

    return Q;

}

// 若队列不空，删除Q的队头元素，用e返回其值，并返回1，否则返回-1

int Q_Poll(LinkQueue *Q,int e) {

    QNodePtr p;

    if (Q->front == Q->rear)

        return -1;

    //取出头节点

    p = Q->front->next;

    //取出头节点的数据

    e = p->data;

    // cout << e << endl;

    Q->front->next = p->next;

    if (Q->rear == p)

        Q->rear = Q->front;

    free(p);

    // cout << e << endl;

    return 1;

}

int main(){

    LinkQueue* Q = Q_Init();
    Q_Put(Q, 1);
    Q_Put(Q, 2);
    Q_Poll(Q, 1);
    Q_Print(Q);
    return 0;
}